package algorithm.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class GreedyAlgorithm {

  public static void main(String[] args) {
    
//    创建电台
    HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

    HashSet<String> hashSet1 = new HashSet<>();
    hashSet1.add("北京");
    hashSet1.add("上海");
    hashSet1.add("天津");

    HashSet<String> hashSet2 = new HashSet<>();
    hashSet2.add("北京");
    hashSet2.add("广州");
    hashSet2.add("深圳");

    HashSet<String> hashSet3 = new HashSet<>();
    hashSet3.add("成都");
    hashSet3.add("上海");
    hashSet3.add("杭州");

    HashSet<String> hashSet4 = new HashSet<>();
    hashSet4.add("上海");
    hashSet4.add("天津");

    HashSet<String> hashSet5 = new HashSet<>();
    hashSet5.add("杭州");
    hashSet5.add("大连");

    broadcasts.put("k1",hashSet1);
    broadcasts.put("k2",hashSet2);
    broadcasts.put("k3",hashSet3);
    broadcasts.put("k4",hashSet4);
    broadcasts.put("k5",hashSet5);

    HashSet<String> allAreas = new HashSet<>();
    allAreas.add("北京");
    allAreas.add("上海");
    allAreas.add("天津");
    allAreas.add("杭州");
    allAreas.add("大连");
    allAreas.add("成都");
    allAreas.add("广州");
    allAreas.add("深圳");

//    System.out.println(allAreas);

//    创建ArrayList，存放我们选择的电台
    ArrayList<String> selects = new ArrayList<>();

//    定义一个临时的集合，在逾历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
    HashSet<String> tempSet = new HashSet<String>();

//    定义给maxKey ,保存在一次追历过程中，能够覆盖最大未覆盖的地区对应的电台的key
//    如果maxKey不为null ,则会加入到selects
    String maxKey;
    
    while (allAreas.size() != 0 ){

      maxKey = null;

      for (String key : broadcasts.keySet()) {
//        注意要清空tempSet
        tempSet.clear();
        //当前这个key能够覆盖的地区
        HashSet<String> areas = broadcasts.get(key);
        //求出tempSet和allAreas的交集，交集会赋给tempSet
        tempSet.addAll(areas);
        tempSet.retainAll(allAreas);

        // tempSet.size() > broadcasts.get(maxKey).size()体现出贪心算法的特点
        if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size() )){
          maxKey = key;
        }
      }

      if (maxKey != null){
        selects.add(maxKey);
        //将maxKey指向的广播电台覆盖的地区，从 allAreas去掉
        allAreas.removeAll(broadcasts.get(maxKey));
      }
    }

    System.out.println("选择的电台是：" + selects);
  }
}
